﻿#include <stdio.h>
#include <stdlib.h>
//直接插入算法
void InsertSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
		int end = i;
		int next = a[i + 1];
		while (end >= 0) {
			if (a[end] > next) {
				a[end + 1] = a[end];
			}
			else {
				break;
			}
			end--;
		}
		a[end + 1] = next;
	}
}
//希尔算法
void ShellSort(int* a, int n) {
	int grab = n;
	//当grab == 1时为直接插入算法，当grab > 1时为预排序
	while (grab != 1) {
		//grab /= 2;
		//以下的grab为改进算法
		grab = grab / 3 + 1;
		for (int j = 0; j < grab; j++) {
			for (int i = j; i < n - grab; i += grab) {
				int end = i;
				int x = a[i + grab];
				while (end >= 0) {
					if (a[end] > x) {
						a[end + grab] = a[end];
					}
					else {
						break;
					}
					end -= grab;
				}
				a[end + grab] = x;
			}
		}
	}
}
//选择算法
void Swap(int* x1, int* x2) {
	int t = *x1;
	*x1 = *x2;
	*x2 = t;
}
void SelectSort(int* a, int n) {
	int begin = 0, end = n - 1;
	while (begin < end) {
		int max = begin, min = begin;
		for (size_t i = begin + 1; i <= end; i++) {
			if (a[max] < a[i]) {
				max = i;
			}
			if (a[min] > a[i]) {
				min = i;
			}
		}
		Swap(a + max, a + end);
		if (min == end) {
			min = max;
		}
		Swap(a + min, a + begin);
		begin++;
		end--;
	}
}

void Print(int* a, int n) {
	for (int i = 0; i < n; i++) {
		fprintf(stdout, "%d ", a[i]);
	}
	puts("");
}
//堆算法
void Adjustdown(int* a, int n, int parent) {
	int child = 2 * parent + 1;
	while (child < n) {
		if (child + 1 < n && a[child] < a[child + 1]) {
			child++;
		}
		if (a[child] > a[parent]) {
			Swap(a + child, a + parent);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
//以升序为例，用建大堆思想
void HeapSort(int* a, int n) {
	//从最后一层走起，因为要保证导入的parent往下都是有序的，即大堆建立
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		Adjustdown(a, n, i);
	}
	//大堆建立后根为最大数，然后进行排序
	int end = n - 1;
	while (end > 0) {
		Swap(a, a + end);//因为根为最大数，要升序就要把最大数放入最后
		Adjustdown(a, end, 0);
		end--;
	}
}
int main() {
	//直接算法
	int a[] = { 5,9,7,3,0,1,4,2,6,8 };
	InsertSort(a, sizeof(a) / sizeof(int));
	Print(a, sizeof(a) / sizeof(int));

	//希尔算法
	int b[] = { 5,9,7,3,0,1,4,2,6,8 };
	ShellSort(b, sizeof(b) / sizeof(int));
	Print(b, sizeof(b) / sizeof(int));

	//选择算法
	int c[] = { 5,9,7,3,0,1,4,2,6,8 };
	SelectSort(c, sizeof(c) / sizeof(int));
	Print(c, sizeof(c) / sizeof(int));

	//堆算法
	int d[] = { 5,9,7,3,0,1,4,2,6,8 };
	HeapSort(d, sizeof(d) / sizeof(int));
	Print(d, sizeof(d) / sizeof(int));
	return 0;
}